// 91. 解码方法
// https://leetcode.cn/problems/decode-ways/description/
// 思路 动态规划

/**
示例 1：

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。


示例 2：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。


示例 3：

输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。
 */

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
    let strArray = s.split('');
    const ret = backTracking(strArray);

    console.log(`${s} is ${JSON.stringify(ret)}`);
    return ret[0] + ret[1];
};

/**
 *
 * @param {*} s
 * @returns [individual,double,lastChar]
 * individual 所有有效排列中，最后一个元素是一位的排列个数
 * double 所有有效排列中，最后一个元素是两位的排列个数
 * 最后一个字符是什么，用于判断26
 */
function backTracking(s) {
    if (s.length <= 0) {
        return [0, 0, null];
    }

    if (s.length === 1) {
        return s[0] === '0' ? [0, 0, '0'] : [1, 0, s[0]];
    }

    let availables = backTracking(s.slice(0, s.length - 1));

    let cur_piece = s[s.length - 1];
    let ret = [0, 0, cur_piece];
    // 独立放
    if (cur_piece !== 0) {
        // 之前独立的和黏连的都保留
        ret[0] = availables[0] + availables[1];
        // ret[1] = availables[1];
    } else {
        // 为0无法独立放，现在总和归零，看下面粘合的
    }

    // 粘合放
    if (cur_piece !== '0') {
        // 新增独立的 判断26 需要将上一字符吐出
        if (availables[2] + cur_piece <= '26') {
            ret[1] = availables[0];
        }
    } else {
        // 之前粘合的都删除，仅保留独立的
        if (availables[2] + cur_piece <= '26') {
            ret[1] = availables[0];
            ret[0] = 0;
        } else {
            ret[1] = 0;
            ret[0] = 0;
        }
    }

    return ret;
}

numDecodings('12'); // 2
numDecodings('226'); // 3
numDecodings('06'); // 0
numDecodings('10'); // 1
numDecodings('2101'); // 1
numDecodings('1123'); // 5
numDecodings('111111111111111111111111111111111111111111111');
numDecodings('230');
